package com.samxcode.leetcode;

/**
 * Given a sorted array and a target value, return the index if the target is found. If not, return
 * the index where it would be if it were inserted in order.
 * 
 * You may assume no duplicates in the array.
 * 
 * solution: binary search
 * 
 * @author Sam
 *
 */
public class SearchInsertPosition {
    
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 6, 8};
        System.out.println(searchInsert(nums, 5));
    }

    public static int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int medium = (left + right) >> 1;
        while (left <= right) {
            if (target == nums[medium]) {
                return medium;
            } else if (target > nums[medium]) {
                left = medium  + 1;
            } else {
                right = medium - 1;
            }
            medium = (left + right) >> 1;
        }
        return left;
    }
}
